
#include "RedBlackTree.h"

template<typename T>
int RedBlackTree<T>::insert(Node* _new)
{
  Node* x = _new;
  BinarySearchTree<T>::insert(x);
  if (x->parent->color == BLACK)
    {
      this->root->color = BLACK;
      return 0;
    }
  while(x->parent != this->nil && x->color == RED)
    {
      if(x->parent == x->parent->parent->left)
	{
	  Node* y = x->parent->parent->right;
	  if(y->color == RED)
	    {
	      x->parent->color = y->color = BLACK;
	      x->parent->parent->color = RED;
	      x = x->parent->parent;
	      if(x->parent->color == BLACK)
		break;
	    }
	  else
	    {
	      if(x == x->parent->right)
		{
		  this->LeftRotate(x->parent);
		  x = x->left;
		}
	      this->RightRotate(x->parent->parent);
	      x->parent->color = BLACK;
	      x->parent->right->color = RED;
	      x = x->parent;
	      break;
	    }
	}
      else if(x->parent == x->parent->parent->right)
	{
	  Node* y = x->parent->parent->left;
	  if(y->color == RED)
	    {
	      x->parent->color = y->color = BLACK;
	      x->parent->parent->color = RED;
	      x = x->parent->parent;
	      if(x->parent->color == BLACK)
		break;
	    }
	  else
	    {
	      if(x == x->parent->left)
		{
		  this->RightRotate(x->parent);
		  x = x->right;
		}
	      this->LeftRotate(x->parent->parent);
	      x->parent->color = BLACK;
	      x->parent->left->color = RED;
	      x = x->parent;
	      break;
	    }
	}
    }
	this->root->color = BLACK;
	return 0;
};

template<typename T>
int RedBlackTree<T>::insert(T _low,T _high)
  {
    Node* t = new Node(_low, _high);
    this->insert(t);
    return 0;
  };

 template<typename T>
 int RedBlackTree<T>::del(Node* _x)
 {
   Node* y = _x;
   bool original_color_y = y->color;
   Node* x;
   if(_x->left == this->nil)
     {
       x = _x->right;
       this->transplant(_x,x);
     }
   else if(_x->right == this->nil)
     {
       x = _x->left;
       this->transplant(_x,x);
     }
   else
     {
       y = this->min(_x->right);
       x = y->right;
       if(y->parent != _x)
	 {
	   this->transplant(y,y->right);
	   y->right = _x->right;
	   y->right->parent = y;
	 }
       this->transplant(_x,y);
       y->left = _x->left;
       y->left->parent = y;
       y->color = _x->color;
     }
   if(original_color_y == BLACK)
     {
       while(x != this->root && x->color == BLACK)
    	    if (x == x->parent->left)
    	    {
    		Node *w = x->parent->right;
    		if (w->color == RED)
    		{
    		    w->color = BLACK;
    		    x->parent->color = RED;
    		    this->LeftRotate(x->parent);
    		    w = x->parent->right;
    		}
    		if (w->left->color == BLACK && w->right->color == BLACK)
    		{
    		    w->color = RED;
    		    x = x->parent;
    		}
    		else
		{
		    if (w->right->color == BLACK)
		    {
			w->left->color = BLACK;
			w->color = RED;
			this->RightRotate(w);
			w = x->parent->right;
		    }
		    w->color = x->parent->color;
		    x->parent->color = BLACK;
		    w->right->color = BLACK;
		    this->LeftRotate(x->parent);
		    x = this->root;
		}
	    }
	    else
     	    {
    		Node *w = x->parent->left;
    		if (w->color == RED)
    		{
    		    w->color = BLACK;
    		    x->parent->color = RED;
    		    this->RightRotate(x->parent);
    		    w = x->parent->left;
    		}
    		if (w->right->color == BLACK && w->left->color == BLACK)
    		{
    		    w->color = RED;
    		    x = x->parent;
    		}
    		else
		{
		    if (w->left->color == BLACK)
		    {
			w->right->color = BLACK;
			w->color = RED;
			this->LeftRotate(w);
			w = x->parent->left;
		    }
		    w->color = x->parent->color;
		    x->parent->color = BLACK;
		    w->left->color = BLACK;
		    this->RightRotate(x->parent);
		    x = this->root;
		}
     	    }
     }
    x->color = BLACK;
    delete _x;
    return 0;    
};
